GATE PYQ

GATE CSE 2017 SET-1

Q41.
The following functional dependencies hold true for the relational schema R{V,W,X,Y,Z}: V \rightarrowW VW \rightarrowX Y\rightarrow VX Y \rightarrowZ Which of the following is irreducible equivalent for this set of functional dependencies ?

Q42.
Consider the following grammar: stmt\rightarrow if expr then else expr; stmt| \dot{O} expr\rightarrowterm relop term|term term\rightarrow id|number if\rightarrowa|b|c number\rightarrow [0-9] where relop is a relational operate (e.g \lt ,\gt,...), \dot{O} refers to the empty statement, and if ,then, else are terminals. Consider a program P following the above grammar containing ten if terminals. The number of control flows paths in P is ____________. For example the program if e_1 then e_3 else e_3 has 2 controls flow paths e_{1} \rightarrow e_{2} and e_{1} \rightarrow e_{3}.

Q43.
Instructions execution in a processor is divided into 5 stages. Instruction Fetch (IF), Instruction Decode (ID) , Operand Fetch (OF), Execute (EX), and Write Back (WB), These stages take 5,4,20, 10 and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2ns. Two pipelined implementations of the processor are contemplated. (i) a naive pipeline implementation (NP) with 5 stages and (ii) an efficient pipeline (EP) where the OF stage id divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively. The speedup (correct to two decimals places) achieved by EP over NP in executing 20 independent instructions with no hazards is ________________.

Q44.
Let X be a Gaussian random variable mean 0 and variance \sigma ^{2} . Let Y=max(X, 0) where max (a,b) is the maximum of a and b. The median of Y is ____________.

Q45.
Consider the first-order logic sentence F:\forall x(\exists yR(x,y)). Assuming non-empty logical domains, which of the sentences below are implied by F? I. \exists y(\exists xR(x,y)) II. \exists y(\forall xR(x,y)) III. \forall y(\exists xR(x,y)) IV. \neg \exists x(\forall y\neg R(x,y))

Q46.
The statement (\neg p)\Rightarrow (\neg q) is logically equivalent to which of the statements below? I. p\Rightarrow q II. q \Rightarrow p III. (\neg q)\vee p IV. (\neg p)\vee q

Q47.
Let p, q, and r be propositions and the expression (p\rightarrowq)\rightarrowr be a contradiction. Then, the expression (r\rightarrowp)\rightarrowq is

Q48.
Consider a database that has the relation schema CR (StudentName, CourseName). An instance of the schema CR is as given below. The following query is made on the database T1\leftarrow \pi _{CourseName}(\sigma _{StudentName='SA'}(CR)) T2\leftarrow CR\div T1 The number of rows in T2 is ____________.

Q49.
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: (I) Minimum spanning tree of G is always unique. (II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true?

Q50.
Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance of the schema EMP and a SQL query on it are given below. The output of executing the SQL query is _____.